package org.example.basic;

import lombok.Data;
import org.example.util.DisJointSet;

import java.io.*;
import java.util.*;

@Data
public class TrussCommunity {

    private int start = 0x3f3f3f3f;

    private int end = 0;

    // 输入的边
    private List<Edge> edgeList;

    // 带有trussness的每条边
    private List<Edge> edgeTrussNess;

    // 邻接表
    private List<AdjacencyEdge> adjacencyEdgeList;

    // 存储边的支持度
    private Map<String, Integer> supMap;

    public void kTrussCommunitySearch(int k, String inputFileName, String outputFileName, String regex) {
        // 读取数据
        readFile(inputFileName, regex);

        if (end - start <= 0) {
            System.out.println("顶点数错误!!!");
            System.out.println("start=" + start + ", end=" + end);
            return;
        }

        trussDecomposition();
        // 输出所有边的trussness
        //writeFile(outputFileName);

        DisJointSet disJointSet = new DisJointSet(end);

        boolean[] flag = new boolean[end + 1];
        for (Edge edge : edgeTrussNess) {
            if (edge.getTrussness() >= k) {
                int u = edge.getU();
                int v = edge.getV();
                disJointSet.join(u, v);
                flag[u] = true;
                flag[v] = true;
            }
        }
        int[] pre = new int[end + 1];

        // 更新每个节点的祖先节点
        for (int i = start; i <= end; ++i) {
            pre[i] = disJointSet.find(i);
//            System.out.printf("pre[%d]=%d\n", i, pre[i]);
        }

        int maxCommunitySize = 0;
        int communityCount = 0;
        int nodeCount = 0;
        for (int i = start; i <= end; ++i) {
            if (flag[i] && pre[i] == i) {
                ++communityCount;
                System.out.printf("第" + communityCount + "个社区的成员为：");
                int num = 0;
                for (int j = start; j <= end; ++j) {
                    if (pre[j] == i) {
                        ++num;
                        System.out.printf("%d ", j);
                    }
                }
                nodeCount += num;
                maxCommunitySize = Math.max(maxCommunitySize, num);
                System.out.println();
                System.out.println("第" + communityCount + "个社区总共有" + num + "个成员");
            }
        }
        System.out.println("共找到" + communityCount + "个" + k + "-truss社区");
        if (communityCount != 0) {
            int avgCommunitySize = nodeCount / communityCount;
            System.out.println("其中最大的社区的大小为" + maxCommunitySize + "，平均社区大小为" + avgCommunitySize);
            dataStatistics(maxCommunitySize, communityCount, avgCommunitySize, k, outputFileName);
        } else {
            dataStatistics(0, 0, 0, k, outputFileName);
        }


    }

    public void dataStatistics(int maxCommunitySize, int communityCount, int avgCommunitySize, int k, String outputFileName) {
        try {
            String line = k + " " + communityCount + " " + maxCommunitySize + " " + avgCommunitySize + "\n";
            FileWriter fileWriter = new FileWriter(outputFileName, true);
            fileWriter.write(line);
            fileWriter.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }


    public void readFile(String inputFileName, String regex) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(inputFileName));
            String line;
            // 标识边(x,y)是否已经存储
            Map<String, Boolean> edgeExist = new HashMap<>();
            edgeList = new ArrayList<>();
            int u, v, x, y;
            String str;
            while ((line = reader.readLine()) != null) {
                // 不是数字则数据不对
                if (line.charAt(0) > '9' || line.charAt(0) < '0') {
                    continue;
                }
                String[] words = line.split(regex);
                if (words.length != 2) {
                    continue;
                }
                u = Integer.parseInt(words[0].trim());
                v = Integer.parseInt(words[1].trim());
                // 去除自环
                if (u == v) {
                    continue;
                }
                start = Math.min(start, Math.min(u, v));
                end = Math.max(Math.max(u, v), end);

                // 无向图使用
                // 小的顶点在前面，大的在后面
                x = Math.min(u, v);
                y = u ^ v ^ x;
                str = x + "-" + y;
                // 去除重边
                if (edgeExist.containsKey(str)) {
                    continue;
                }
                edgeExist.put(str, true);
                edgeList.add(new Edge(x, y, 0));
            }
            reader.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * // 无向图添加边
     *
     * @param first
     * @param degree
     * @return
     */
    private void addEdge(int[] first, int[] degree) {
        for (int i = start; i <= end; ++i) {
            first[i] = -1;
        }
        adjacencyEdgeList = new ArrayList<>();
        //todo 待优化
        int size = 0;

        // 添加边
        // 使用邻接表存储
        for (Edge edge : edgeList) {
            int u = edge.getU();
            int v = edge.getV();
            adjacencyEdgeList.add(new AdjacencyEdge(v, first[u]));
            first[u] = size++;
            ++degree[u];
            adjacencyEdgeList.add(new AdjacencyEdge(u, first[v]));
            first[v] = size++;
            ++degree[v];
        }
    }

    public String getSupKey(int x, int y) {
        return Math.min(x, y) + "-" + Math.max(x, y);
    }

    private void computeSup(int[] first, int[] degree) {
        int x;
        int y;
        String edgeKey;
        supMap = new HashMap<>();
        for (Edge edge : edgeList) {// 对于边(x,y)
            // 小的顶点在前面，大的顶点在后面
            edgeKey = getSupKey(edge.getU(), edge.getV());
            // 去除重边的支持度的计算
            if (supMap.containsKey(edgeKey)) {
                continue;
            }
            // 令x为度较小的顶点
            if (degree[edge.getU()] <= degree[edge.getV()]) {
                x = edge.getU();
                y = edge.getV();
            } else {
                x = edge.getV();
                y = edge.getU();
            }
            int sup = 0;
            for (int i = first[x]; i != -1; i = adjacencyEdgeList.get(i).getNext()) {
                int z = adjacencyEdgeList.get(i).getV();// 得到边(x,z)
                for (int j = first[y]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                    if (adjacencyEdgeList.get(j).getV() == z) {// 若存在边(y,z),则边(x,y)的支持度加1
                        edge.increaseSup();
                        ++sup;
                    }
                }
            }
            supMap.put(edgeKey, sup);
        }
    }

    private void writeFile(String outputFileName) {
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName));
            int maxTruss = 0;
            for (Edge edge : edgeTrussNess) {
                maxTruss = Math.max(maxTruss, edge.getTrussness());
                System.out.printf("边(%d,%d)：sup=%d, trussness=%d\n", edge.getU(), edge.getV(), edge.getSup(), edge.getTrussness());
                writer.write("边(" + edge.getU() + "," + edge.getV() + ")：sup=" + edge.getSup() + ", trussness=" + edge.getTrussness() + "\n");

            }
            writer.write("maxTruss=" + maxTruss);
            writer.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void trussDecomposition() {
        int[] first = new int[end + 1];
        int[] degree = new int[end + 1];
        edgeTrussNess = new ArrayList<>();

        // 添加边
        addEdge(first, degree);

        // 为每条边计算sup(e)
        computeSup(first, degree);

        int k = 2;
        int x;
        int y;
        while (!edgeList.isEmpty()) {
            // 对边按支持度进行升序排序
            Collections.sort(edgeList);

            Iterator<Edge> iterator = edgeList.iterator();
            int sup = k - 2;
            while (iterator.hasNext()) {
                Edge edge = iterator.next();
                String xy_supKey = getSupKey(edge.getU(), edge.getV());
                if (supMap.get(xy_supKey) <= sup) {
                    // 删除该边
                    edgeTrussNess.add(new Edge(edge.getU(), edge.getV(), edge.getSup(), k));
                    iterator.remove();
                    // 边(x,y)的支持度为-1表示该边已经被删除了
                    supMap.put(xy_supKey, -1);
                    --degree[edge.getU()];
                    --degree[edge.getV()];

                    // 令x为度较小的顶点
                    if (degree[edge.getU()] <= degree[edge.getV()]) {
                        x = edge.getU();
                        y = edge.getV();
                    } else {
                        x = edge.getV();
                        y = edge.getU();
                    }
                    // 更新在同一个三角形中其它边的sup
                    for (int i = first[x]; i != -1; i = adjacencyEdgeList.get(i).getNext()) {
                        int z = adjacencyEdgeList.get(i).getV();// 得到边(x,z)
                        String xz_supKey = getSupKey(x, z);
                        // 若该边已经被删除了，则跳过
                        if (supMap.get(xz_supKey) == -1) {
                            continue;
                        }
                        for (int j = first[y]; j != -1; j = adjacencyEdgeList.get(j).getNext()) {
                            if (adjacencyEdgeList.get(j).getV() == z) {// 若存在边(y,z),则边(x,y)、(x,z)、(y,z)在一个三角形中
                                String yz_supKey = getSupKey(y, z);
                                // 若该边已经被删除了，则跳过
                                if (supMap.get(yz_supKey) == -1) {
                                    continue;
                                }
                                supMap.put(xz_supKey, supMap.get(xz_supKey) - 1);
                                supMap.put(yz_supKey, supMap.get(yz_supKey) - 1);
                            }
                        }
                    }
                }
            }
            ++k;
        }
    }

    public void kTrussCommunitySearchNoRead(int k, String outputFileName) {
        trussDecomposition();

        DisJointSet disJointSet = new DisJointSet(end);

        boolean[] flag = new boolean[end + 1];
        for (Edge edge : edgeTrussNess) {
            if (edge.getTrussness() >= k) {
                int u = edge.getU();
                int v = edge.getV();
                disJointSet.join(u, v);
                flag[u] = true;
                flag[v] = true;
            }
        }
        int[] pre = new int[end + 1];

        // 更新每个节点的祖先节点
        for (int i = start; i <= end; ++i) {
            pre[i] = disJointSet.find(i);
//            System.out.printf("pre[%d]=%d\n", i, pre[i]);
        }

        int maxCommunitySize = 0;
        int communityCount = 0;
        int nodeCount = 0;
        for (int i = start; i <= end; ++i) {
            if (flag[i] && pre[i] == i) {
                ++communityCount;
                System.out.printf("第" + communityCount + "个社区的成员为：");
                int num = 0;
                for (int j = start; j <= end; ++j) {
                    if (pre[j] == i) {
                        ++num;
                        System.out.printf("%d ", j);
                    }
                }
                nodeCount += num;
                maxCommunitySize = Math.max(maxCommunitySize, num);
                System.out.println();
                System.out.println("第" + communityCount + "个社区总共有" + num + "个成员");
            }
        }
        System.out.println("共找到" + communityCount + "个" + k + "-truss社区");
        if (communityCount != 0) {
            int avgCommunitySize = nodeCount / communityCount;
            System.out.println("其中最大的社区的大小为" + maxCommunitySize + "，平均社区大小为" + avgCommunitySize);
            dataStatistics(maxCommunitySize, communityCount, avgCommunitySize, k, outputFileName);
        } else {
            dataStatistics(0, 0, 0, k, outputFileName);
        }

    }

}
